/*
 * Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, 
compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
 */
package com.xinpan.exercise;

public class TrappingRainWater {
    public int trap(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(A.length < 3)
            return 0;
        
        int sum = 0;
        for(int i = 0; i < A.length-2; i++)
        {
            if(A[i+1] >= A[i])
                continue;
            int deep = A[i] - A[i+1];
            
            for(int j = 1; j <= A[i]- A[i+1]; j++)
            {
                int l = i+2;
                while(l < A.length && A[l] <= A[i]-j) l++;
                if(l != A.length)
                    sum += l-i-1;
            }

        }
        return sum;
    }
}
